/**
 * Created by IntelliJ IDEA.
 * User: Taras_Brzezinsky
 * Date: 8/24/11
 * Time: 8:54 PM
 * To change this template use File | Settings | File Templates.
 */

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.util.Arrays;

public class TaskD extends Thread {

    public TaskD() {
        this.input = new BufferedReader(new InputStreamReader(System.in));
        this.output = new PrintWriter(System.out);
        this.setPriority(Thread.MAX_PRIORITY);
    }

    private int getIndex(int[][] data, int[] values) {
        for (int i = 0; i < data.length; ++i) {
            if (Arrays.equals(data[i], values)) {
                return i;
            }
        }
        throw new IllegalArgumentException();
    }

    private void generate(int index) {
        if (index == helper.length) {
            states[SIZE++] = helper.clone();
        } else {
            for (int value = 0; value < v[index]; ++value) {
                helper[index] = value;
                generate(index + 1);
            }
        }
    }

    private int[][] pow(int[][] src, long power) {
        int[][] result = new int[src.length][src.length];
        for (int i = 0; i < result.length; ++i) {
            result[i][i] = 1;
        }
        for (; power != 0; power >>= 1) {
            if ((power & 1) == 1) {
                result = multiply(result, src);
            }
            src = multiply(src, src);
        }
        return result;
    }

    private int[][] multiply(int[][] left, int[][] right) {
        int[][] result = new int[left.length][left.length];
        for (int i = 0; i < left.length; ++i) {
            for (int j = 0; j < left.length; ++j) {
                for (int k = 0; k < left.length; ++k) {
                    result[i][j] += (left[i][k] * right[k][j]) % MODULO;
                }
                result[i][j] %= MODULO;
            }
        }
        return result;
    }

    private void solve() throws Throwable {
        long n = nextLong();
        int c = nextInt();
        l = new int[c];
        v = new int[c];
        boolean[] used = new boolean[AlPHABET_SIZE], good = new boolean[AlPHABET_SIZE];

        int total = 1;
        for (int i = 0; i < c; ++i) {
            l[i] = nextToken().charAt(0) - 'A';
            used[l[i]] = true;
            total *= (v[i] = nextInt());
        }
        states = new int[total][];
        helper = new int[c];
        generate(0);
        int[][] grid = new int[total][total];
        for (int current = 0; current < total; ++current) {
            for (int i = 0; i < AlPHABET_SIZE; ++i) {
                helper = states[current].clone();
                if (used[i]) {
                    for (int ind = 0; ind < c; ++ind) {
                        if (l[ind] == i) {
                            helper[ind] = (helper[ind] + 1) % v[ind];
                        }
                    }
                    grid[current][getIndex(states, helper)]++;
                }
            }
        }
        int[][] result = pow(grid, n);
        int answer = 0;
        for (int currentState = 0; currentState < total; ++currentState) {
            Arrays.fill(good, false);
            for (int i = 0; i < c; ++i) {
                good[l[i]] |= states[currentState][i] == 0;
            }
            boolean can = true;
            for (int i = 0; i < AlPHABET_SIZE; ++i) {
                if (used[i] && !good[i]) {
                    can = false;
                    break;
                }
            }
            if (can) {
                answer = (answer + result[0][currentState]) % MODULO;
            }
        }
        output.println(answer);
    }

    public void run() {
        try {
            solve();
        } catch (Throwable e) {
            System.err.println(e.getMessage());
            e.printStackTrace();
            System.exit(666);
        } finally {
            output.flush();
            output.close();
        }
    }


    public static void main(String[] args) {
        new TaskD().start();
    }

    private String nextToken() throws IOException {
        while (tokens == null || !tokens.hasMoreTokens()) {
            tokens = new StringTokenizer(input.readLine());
        }
        return tokens.nextToken();
    }

    private int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    private double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    private long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    private static int[][] states;
    private int[] helper, l, v;
    private static int SIZE = 0;
    private static final int MODULO = 12345, AlPHABET_SIZE = 26;
    private BufferedReader input;
    private PrintWriter output;
    private StringTokenizer tokens = null;
}